#include <stdio.h>
#include <stdlib.h>

const int MAX_CITY = 100;
const int MAX_COST = 100000000;

/**
 * Retorna o menor valor entre os dois passados como argumento
 *
 * @param i o primeiro valor
 * @param j o segundo valor
 *
 * @return o menor valor entre i e j
 */
int min(int i, int j) {
    return i < j ? i : j;
}

/********************************************************************************
 * Problema da disciplina de Estrutura de Dados e Complexidade de Algoritmos da *
 * Pos Graduacao do Periodo 2011.1                                              *
 *                                                                              *
 * @see http://br.spoj.pl/problems/MINIMO/                                      *
 * @author Elenilson Vieira - 111100371 - elenilson[at]elenilsonvieira.com      *
 * @since 5 de julho de 2011                                                    *
 ********************************************************************************/
int main(int argc, char** argv) {

    int cityAmouont = 0, scaleAmount = 0, queryAmount = 0, instance = 1, maxCitiesToScale = 0;
    int graph[MAX_CITY + 1][MAX_CITY][MAX_CITY];
    int i = 0, j = 0, k = 0, l = 0;
    int cityU = 0, cityV = 0, costUV = 0;

    while(scanf("%d %d", &cityAmouont, &scaleAmount) != EOF){
        /*** Inicia o array de distancias ***/
        for(i = 0; i < cityAmouont; i++)
            for(j = 0; j < cityAmouont; j++)
                    graph[0][i][j] = i != j ? MAX_COST : 0;

        /*** Ler as cidades e os custos ***/
        for(i = 0; i < scaleAmount; i++){
            scanf("%d %d %d", &cityU, &cityV, &costUV);
            
            if(graph[0][cityU - 1][cityV - 1] > costUV)
                graph[0][cityU - 1][cityV - 1] = costUV;
        }

        /*** Ler a quantidade de consultas ***/
        scanf("%d", &queryAmount);

        /*** Faz os calculos com floyd ***/
        for(k = 1; k <= cityAmouont; k++)
            for(i = 0; i < cityAmouont; i++)
                for(j = 0; j < cityAmouont; j++)
                    graph[k][i][j] = min(graph[k - 1][i][j], graph[k - 1][i][k - 1]+graph[k - 1][k - 1][j]);

        printf("Instancia %d\n", instance++);

        /*** Ler as consultas ***/
        for(l = 0; l < queryAmount; l++){
            costUV = -1;
            
            /*** Ler a consulta ***/
            scanf("%d %d %d", &cityU, &cityV, &maxCitiesToScale);

            if(graph[maxCitiesToScale][cityU - 1][cityV - 1] != MAX_COST)
                costUV = graph[maxCitiesToScale][cityU - 1][cityV - 1];

            /*** Imprime o resultado ***/
            printf("%d\n", costUV);
        }

        printf("\n");

    }

    return (EXIT_SUCCESS);
}